https://www.lintcode.com/problem/two-sum/my-submissions?_from=ladder&&fromId=6

class Solution {
public:
    /**
     * @param numbers: An array of Integer
     * @param target: target = numbers[index1] + numbers[index2]
     * @return: [index1, index2] (index1 < index2)
     */
    // O(N^2)
    // vector<int> twoSum(vector<int> &numbers, int target) {
    //     vector<int> result;
    //     for (int i = 0; i < numbers.size(); ++i)
    //     {
    //         for (int j = i + 1; j < numbers.size(); ++j)
    //         {
    //             if (numbers[i] + numbers[j] == target)
    //             {
    //                 result.push_back(i);
    //                 result.push_back(j);
    //                 return result;
    //             }
    //         }
    //     }
    //     return result;
    // }
    
    // O(N)
    vector<int> twoSum(vector<int> &numbers, int target) {
        map<int, int> record_map;
        vector<int> result;
        for (int i = 0; i < numbers.size(); ++i)
        {
            if (record_map.find(numbers[i]) != record_map.end()) 
            {
                result.push_back(record_map[numbers[i]]);
                result.push_back(i);
            }
            record_map[target - numbers[i]] = i;
        }
        return result;
    }        
};